Generational GC(世代別GC)

概要

「多くのオブジェクトは若くして死ぬ」という説に基づく手法

世代別仮設

オブジェクトに年齢の概念を導入する

一回のGCを経て生き残ったオブジェクトは1歳

Mark Sweep GCやCopiyng GCは生きているオブジェクトだけを辿るので、多くが死ぬ新世代のオブジェクトのみを見ればGCにかかる時間を短縮できるはず

基本的に他のGCと併用する

新世代オブジェクトと旧世代オブジェクト

新世代オブジェクト

生成されたばかりのオブジェクト

新世代オブジェクトに対するGCをminor GCと呼ぶ

minor =「小規模な」

旧世代オブジェクト

一定の年齢に達したオブジェクト

旧世代オブジェクトに対するGCをmajor GCと呼ぶ

新世代オブジェクト→旧世代オブジェクトへと世代を上げることを「昇格(promotion)」や「殿堂入り(tenuring)」などという

Ungarの世代別GC

Copying GC + Generational GC

ヒープの4領域と、ヒープとは別の場所の記憶集合という配列を使う

ヒープを4つにわける(括弧中は論文でのサイズ)

生成領域(140KB)

オブジェクトの生成を行う領域。いっぱいになるとminor GC発動

コピーGCと同じ要領で生存領域1にコピーされる

minor GC時は通常のGCのルートに加え、旧世代領域からの参照も確認する必要がある

アロケートするオブジェクトのサイズが空いているかチェックし、足りなかったらminorGCを起こす。

生成領域のサイズ(ここでは140KB)より大きなオブジェクトの場合、アロケートできないが、ここで、旧世代領域へアロケートするという方針を取ることもある

生存領域1、生存領域2(28KB)

同じサイズ

コピーGCのto, from空間と同じ関係。どっちかが常に空

minor GCが起こると生成領域とFrom空間からTo空間へコピーする

旧世代領域(940KB)

何度かのminor GCで生き残ったオブジェクトがコピーされる

この領域内でのGC(major GC)では普通のMark Sweep GC

旧世代領域がいっぱいになるとMajorGCを実行する

記憶集合

固定サイズの配列。要素はオブジェクトへのポインタ

毎度旧世代領域の全てのオブジェクトをスキャンすると世代別GCのメリットが発揮されないので、新世代領域への参照を持っているかどうかを記憶集合にメモっておく

minor GC時に記憶集合をルートとみなしてスキャンし、新世代領域へのポインタを発見するのに利用する

デメリット

参照元のオブジェクトを直接記録するので、1つの参照元オブジェクトに対して1ワード消費するのでメモリ領域の使用効率が良くない

記憶集合に代わる別の方法

Card Marking

旧世代領域を一定サイズに分割し、それをカードと呼ぶ

128byteが適しているらしい(論文)

カードごとにカード内のオブジェクトが新世代領域への参照を持っているかどうかのフラグを立てる

Mark Sweep GCのビットマップテーブルのようなイメージ

GC時にはビットマップテーブルをスキャンし、フラグがアレばそのカードをスキャンし新世代領域への参照を見つける

メリット

メモリ領域の使用効率がいい

オーバーフローすることがない

デメリット

フラグが立ちまくると遅くなる

Page Marking

カードのサイズをOSのページのサイズと同じにする

旧世代領域のあるページへ書き込みを行うとOSがそのページに対応したビットを立てる。←「ダーティビット」と呼ぶ

ダーティビットを使用できないOSは、代わりにメモリ保護機能を利用する

Multi-generational GC(複数世代管理GC)

新世代、第2世代、... 、第n世代領域と分ける

第n世代記憶集合には1~n-1の参照のみを記録

二世代、三世代くらいがいいらしい

Train GC(トレインGC)

世代別GCのMajorGCで利用するアルゴリズム

未読！！！！！！！！！！！！！！

Write barrier

旧世代オブジェクトを記憶集合へ記録しておくために使用

旧世代オブジェクトから新世代オブジェクトへの参照を追加するタイミングを監視する

メリット

スループットの改善

minorGCの時間が少ない+MajorGCの頻度がめっちゃ少ない

Ungar「実験するとコピーGCの1/4になったわ」

デメリット

「多くのオブジェクトは若くして死ぬ」というのが成り立たない場合は逆効果

MinorGCにかかる時間が増大

MajorGCが多発

WriteBarrierのオーバーヘッド

MajorGCに時間がかかるため最大停止時間は大きい

ヘッダに格納するもの

オブジェクトの種類、サイズ

オブジェクトの年齢

新世代で使う

コピー済みフラグ

新世代で使う

記憶集合への記録済みフラグ

旧世代で使う

Generational GCが用いられている言語

Rubinius

3歳になると旧世代領域へ行く(2回GCが実行されると旧世代オブジェクトになる)

MajorGCはImmixというGCアルゴリズムを使う

連続した領域に有効なオブジェクトを集めることで、使用する総メモリ量とヒープの断片化の量を減らそうとする

巨大なオブジェクト用に3つ目の世代を使用し、MarkSweepGCを使う